package arithmetic1.tree.binaryTree;

/*
    链式二叉树
 */
public class BinaryTree {
    //二叉树的根节点
    private Hero root;

    public BinaryTree(Hero root) {
        this.root = root;
    }

    //先序遍历
    public void perOrder(Hero root){
        if(root!=null){
            System.out.print(root+"\t");
            if(root.getLeft()!=null){   //向左遍历
                perOrder(root.getLeft());
            }
            if(root.getRight()!=null){  //向右遍历
                perOrder(root.getRight());
            }
        }
    }
    public void perOrder(){
        perOrder(this.root);
    }

    //中序遍历
    public void infixOrder(Hero root){
        if(root!=null){
            if(root.getLeft()!=null){
                infixOrder(root.getLeft());
            }
            System.out.print(root+"\t");
            if(root.getRight()!=null){
                infixOrder(root.getRight());
            }
        }
    }
    public void infixOrder(){
        infixOrder(this.root);
    }

    //后序遍历
    public void afterOrder(Hero root){
        if(root!=null){
            if(root.getLeft()!=null){
                afterOrder(root.getLeft());
            }
            if(root.getRight()!=null){
                afterOrder(root.getRight());
            }
            System.out.print(root+"\t");
        }
    }
    public void afterOrder(){
        afterOrder(this.root);
    }

    //先序查找
    public Hero perFind(int id,Hero root){
        Hero hero=null;
        if(root!=null){     //树不为空时
            if(root.getId()==id){
                hero=root;
            }
            if(hero!=null){
                return hero;
            }
            if(root.getLeft()!=null){       //向左查找
                hero=perFind(id,root.getLeft());
            }
            if(hero!=null){     //在左边已经找到
                return hero;
            }
            if(root.getRight()!=null){
                hero=perFind(id,root.getRight());
            }
        }
        return hero;
    }
    public Hero perFind(int id){
        return this.perFind(id,root);
    }

    //中序查找
    public Hero infixFind(int id,Hero root){
        Hero hero=null;
        if (root!=null) {
            if(root.getLeft()!=null){       //向左查找
                hero=perFind(id,root.getLeft());
            }
            if(hero!=null){
                return hero;
            }
            if(root.getId()==id){
                hero=root;
            }
            if(hero!=null){
                return hero;
            }
            if(root.getRight()!=null){  //向右找
                hero=perFind(id,root.getRight());
            }
        }
        return hero;
    }
    public Hero infixFind(int id){
        return infixFind(id,root);
    }

    //后序查找
    public Hero afterFind(int id,Hero root){
        Hero hero=null;
        if(root!=null){
            if(root.getLeft()!=null){       //向左查找
                hero=perFind(id,root.getLeft());
            }
            if(hero!=null){
                return hero;
            }
            if(root.getRight()!=null){  //向右找
                hero=perFind(id,root.getRight());
            }
            if(hero!=null){
                return hero;
            }
            if(root.getId()==id){
                hero=root;
            }
        }
        return hero;
    }
    public Hero afterFind(int id){
        return afterFind(id,root);
    }

    //删除子节点 如果该节点是叶子节点，删除该叶子节点。如果不是叶子节点，删除该子树
    public void remove(int id,Hero root){
        if(root!=null){     //当树不为空时才有必要进行删除
            if(root.getId()==id){   //删除的是根节点时
                this.root=null;
                return;
            }
            //删除的不是根节点
            if(root.getLeft()!=null && root.getLeft().getId()==id){ //删除的是该节点的左子节点
                root.setLeft(null);
                return;
            }else {     //向左递归
                remove(id,root.getLeft());
            }
            if(root.getRight()!=null && root.getRight().getId()==id){   //删除的是该节点的右子节点
                root.setRight(null);
                return;
            }else {     //向右递归
                remove(id,root.getRight());
            }
        }
    }
    public void remove(int id){
        remove(id,root);
    }

}

//节点类型
class Hero{
    private int id;
    private String name;
    //左边节点
    private Hero left;
    //右边节点
    private Hero right;

    public Hero(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Hero getLeft() {
        return left;
    }

    public void setLeft(Hero left) {
        this.left = left;
    }

    public Hero getRight() {
        return right;
    }

    public void setRight(Hero right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Hero{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
//测试
class Test{
    public static void main(String[] args) {
        //创建根节点
        Hero hero1=new Hero(1,"宋江");
        //创建二叉树
        BinaryTree binaryTree=new BinaryTree(hero1);
        //创建节点
        Hero hero2=new Hero(2,"吴用");
        Hero hero3=new Hero(3,"卢俊义");
        Hero hero4=new Hero(4,"晁盖");
        Hero hero5=new Hero(5,"林冲");
        hero1.setLeft(hero2);
        hero1.setRight(hero3);
        hero2.setLeft(hero4);
        hero3.setRight(hero5);
        System.out.println("先序遍历:");
        binaryTree.perOrder();
//        arithmetic1.tree.binaryTree.infixOrder();
//        arithmetic1.tree.binaryTree.afterOrder();
        System.out.println("\n-----------------");
//        Hero hero=arithmetic1.tree.binaryTree.perFind(5);
//        Hero hero=arithmetic1.tree.binaryTree.infixFind(5);
//        System.out.println(hero);

        binaryTree.remove(2);
        binaryTree.remove(5);
        System.out.println("先序遍历:");
        binaryTree.perOrder();
    }
}
